﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Inspired.Euler
{
    public static class Problem024
    {
        public static long Solve()
        {
            return Convert.ToInt64(new[]{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
                   .Permutation(999999));
        }

        static string Permutation<T>(this T[] numbers, int num)
        {
            int factorial = 1;
            for (int i = 2; i < numbers.Length; i++)
                factorial *= i; // calculates the factorial of (s.length - 1)

            for (int i = 0; i < numbers.Length - 1; i++)
            {
                int tempi = (num / factorial) % (numbers.Length - i);
                T temp = numbers[i + tempi];
                for (int j = i + tempi; j > i; j--)
                    numbers[j] = numbers[j - 1];

                numbers[i] = temp; // put the chosen cell in the correct spot
                factorial /= (numbers.Length - (i + 1)); // updates the factorial
            }

            return String.Join("", numbers);
        }
    }
}
